package tree;

/**
 * 2-3树
 * 
 * @author mengxin
 * 
 */
public class Tree23 {
	private class TTNode {
		Object lKey;
		Object rKey;
		TTNode leftNode;
		TTNode centNode;
		TTNode rightNode;

		public TTNode() {
			leftNode = centNode = rightNode = null;
			lKey = rKey = -1;
		}

		boolean isLeaf() {
			return leftNode == null;
		}
	}

	private boolean findHelp(TTNode subroot, Object key) {
		if (subroot == null)
			return false;
		if ((Integer) key == (Integer) subroot.lKey) {
			return true;
		}
		if ((Integer) subroot.rKey != -1
				&& (Integer) key == (Integer) subroot.rKey) {
			return true;
		}
		if ((Integer) key < (Integer) subroot.lKey) {
			return findHelp(subroot.leftNode, key);
		} else if ((Integer) subroot.rKey == -1) {
			return findHelp(subroot.centNode, key);
		} else if ((Integer) key < (Integer) subroot.rKey) {
			return findHelp(subroot.centNode, key);
		} else {
			return findHelp(subroot.rightNode, key);
		}
	}

	public Object splitNode(TTNode subroot, Object inval, TTNode inptr,
			TTNode retptr) {
		retptr = new TTNode();
		Object retval;
		if ((Integer) inval < (Integer) subroot.lKey)// subroot.lKey是中间值
		{
			retval = subroot.lKey;// 把中间值传递给返回值
			subroot.lKey = inval;// 把当前结点分成两个结点，一个是subroot，一个是retptr
			retptr.lKey = subroot.rKey;// 吧subroot的右值赋给retptr的左值
			retptr.leftNode = subroot.centNode;// 把subroot的中子树赋给retptr的左子树
			retptr.centNode = subroot.rightNode;// 把subroot的右子树赋给retptr的中子树
			subroot.centNode = inptr;// 把下面升上来的子树赋值给subroot的中子树
			subroot.rKey = -1;// 把subroot的右值清空
			return retval;
		} else if ((Integer) inval < (Integer) subroot.rKey)// 中间值是inval,即要插入的值
		{
			retval = inval;
			retptr.lKey = subroot.rKey;// 吧subroot的右值赋给retptr的左值
			retptr.leftNode = inptr;// 把下面升上来的子树赋值给retptr的左子树
			retptr.centNode = subroot.rightNode;//
			subroot.rKey = -1;// 把subroot的右值清空
			return retval;
		} else {// 中间值是subroot.rKey
			retval = subroot.rKey;
			retptr.lKey = inval;
			retptr.leftNode = subroot.rightNode;
			retptr.centNode = inptr;
			subroot.rKey = -1;
			return retval;
		}
	}

	public Object insertHelp(TTNode subroot, Object key, TTNode retptr) {
		Object myretv = null;
		TTNode myretp = null;
		if (subroot == null)// 如果树是空的，初始化一个结点
		{
			subroot = new TTNode();
			subroot.lKey = key;
		} else if (subroot.isLeaf())// 如果当前结点是叶结点
		{
			if ((Integer) subroot.rKey == -1)// 右值为空
			{
				if ((Integer) key > (Integer) subroot.lKey)// 插入关键码大于左值
				{
					subroot.rKey = key;// 直接插入到右值
				} else // 否则
				{
					subroot.rKey = subroot.lKey;// 左值赋值给右值
					subroot.lKey = key;// 插入到左值
				}
			} else // 右值不为空
			{
				myretv = splitNode(subroot, key, null, retptr);// 分裂该结点
			}
		} else if ((Integer) key < (Integer) subroot.lKey)// 如果待插入小于左值
		{
			myretv = insertHelp(subroot.leftNode, key, myretp);// 那么要插入的叶结点在它的左子树上
		} else if ((Integer) subroot.rKey == -1
				|| (Integer) key < (Integer) subroot.rKey)// 如果当前节点右值为空或待插入值小于右值
		{
			myretv = insertHelp(subroot.centNode, key, myretp);// 那么要插入的叶结点在它的中子树上
		} else // 其他
		{
			myretv = insertHelp(subroot.rightNode, key, myretp);// 那么要插入的叶结点在它的右子树上
		}

		if (myretp != null)// 如果下面传递过来的分裂子树不为空
		{
			if ((Integer) subroot.rKey != -1)// 如果右值不为空
			{
				myretv = splitNode(subroot, myretv, myretp, retptr);// 分裂当前节点
			} else {// 否则，即右值为空
				if ((Integer) myretv < (Integer) subroot.lKey)// 传上来的中值小于当前结点的左值
				{
					subroot.rKey = subroot.lKey;// 将当前结点的左值赋值给右值
					subroot.lKey = myretv;// 将传上来的值赋值给左值
					subroot.rightNode = subroot.centNode;// 将中子树赋给右子树
					subroot.centNode = myretp;// 将传上来的分裂子树赋值给中子树
				} else {// 否则，即传上来的值大于等于左值
					subroot.rKey = myretv;// 直接将传上来的值赋值给右值
					subroot.rightNode = myretp;// 传上来的分裂结点赋值给右结点
				}
			}
		}
		return myretv;
	}
}
